package CommonAlgs.DP;

/**
 * @Author ChanZany
 * @Date 2021/5/14 14:46
 * @Version 1.0
 * 最长公共子序列
 * 构建table，用dp来解决
 * 0 a b c
 * 0 0 0 0 0
 * b 0 0 1 1  <-(if b!=c b||abc=b||ab)
 * c 0 0 1 2  <-(if c!=b bc||ab=b||ab if c==c bc||abc=b||ab+1)
 */
public class LCS {

    public static void main(String[] args) {
        String A = "abcde";
        String B = "ace";
        int res = dpSolustion(A, B);
        System.out.println(res);
    }

    private static int dpSolustion(String a, String b) {
        int m = a.length(), n = b.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char c1 = a.charAt(i), c2 = b.charAt(j);
                if (c1 == c2) dp[i + 1][j + 1] = dp[i][j] + 1;
                else dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);
            }
        }
        return dp[m][n];
    }

}
